package leet;

/**
 * Best Time to Buy and Sell Stock with Transaction Fee
 * 
 * @author zhujb
 *
 *         2017年11月3日
 */
public class Leet0714 {

	public static void main(String[] args) {
		int[] prices = { 1, 3, 2, 8, 4, 9 };
		int fee = 2;

		System.out.println("结果：" + new Leet0714().maxProfit(prices, fee));

	}

	/**
	 * 卖点，买点 (卖出价，买点后的最大值，卖点比后一天价格高fee且比买点高fee) .（买价，买点为卖点前，上一个卖点后的最低值）
	 * 
	 * @param prices
	 * @param fee
	 * @return
	 */
	public int maxProfit(int[] prices, int fee) {

		if (prices.length < 2) {
			return 0;
		}

		int buy = prices[0];
		int sell = prices[0];
		int sum = 0;

		for (int i = 1; i < prices.length; i++) {
			// 触发卖操作
			if (sell - prices[i] > fee && sell - buy > fee) {
				sum += sell - buy - fee;
				buy = prices[i];
				sell = prices[i];
			} else {

				// 预存买价
				if (buy > prices[i]) {
					buy = prices[i];
					sell = prices[i];
				} else {

					if (sell < prices[i]) {
						sell = prices[i];
					}

				}

			}

		}

		if (sell - buy > fee) {
			sum += sell - buy - fee;
		}

		return sum;
	}

}
